#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<unordered_set>
using namespace std;

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> edges;
        queue<int> Q;
        vector<int> in(n);
        vector<int> ret;
        for (auto e : prerequisites)
        {
            edges[e[1]].push_back(e[0]);
            ++in[e[0]];
        }
        for (int i = 0; i < n; ++i)
        {
            if (in[i] == 0)
                Q.push(i);
        }
        while (Q.size())
        {
            int num = Q.front();
            Q.pop();
            ret.push_back(num);
            for (auto e : edges[num])
            {
                --in[e];
                if (in[e] == 0)
                    Q.push(e);
            }
        }

        for (int i = 0; i < n; ++i)
            if (in[i] != 0)
                return {};

        return ret;
    }

    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int> in;
        queue<char> Q;

        for (auto w : words)
        {
            for (auto c : w)
                in[c] = 0;
        }

        for (int i = 0; i < words.size(); ++i)
        {
            for (int j = i + 1; j < words.size(); ++j)
            {
                string s1 = words[i], s2 = words[j];
                int p = 0, n = min(s1.size(), s2.size());
                for (; p < n; ++p)
                {
                    char a = s1[p], b = s2[p];
                    if (a != b)
                    {
                        if (!edges.count(a) || !edges[a].count(b))
                        {
                            edges[a].insert(b);
                            ++in[b];
                        }
                        break;
                    }
                }
                if (p == s2.size() && p < s1.size())
                    return "";
            }
        }

        for (auto& [k, v] : in)
            if (v == 0)
                Q.push(k);

        string ret;
        while (Q.size())
        {
            char c = Q.front();
            Q.pop();
            ret += c;
            for (auto e : edges[c])
            {
                if (--in[e] == 0)
                    Q.push(e);
            }
        }
        for (auto& [k, v] : in)
        {
            if (v != 0) return "";
        }
        return ret;
    }
};